import java.io.*;
import java.util.*;

public class test {
    public static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static Read in = new Read();
    public static int sum;
    // 蓝桥杯 分糖果(⭐⭐⭐)
    public static void main(String[] args) throws IOException {
        dfs(9,16,1);
        System.out.println(sum);
    }
    public static void dfs(int n,int m,int key){
        if(key == 8){
            if(n == 0 && m == 0){
                sum++;
            }
            return;
        }
        for(int i = 0;i <= n;i++){
            for(int j = 0;j <= m;j++){
                if(i + j >= 2 && i + j <= 5){
                    dfs(n - i,m - j,key + 1);
                }
            }
        }
    }
    // 蓝桥杯 合唱队形(⭐⭐⭐)
    public static void main1(String[] args) throws IOException{
        int n = in.nextInt();
        //目标:k位同学排成合唱队形
        //合唱队形:左一部分严格递增,右一部分严格递减
        int[] arr = new int[n + 1];
        for(int i = 1;i <= n;i++) {
            arr[i] = in.nextInt();
        }
        //代表以i位置结尾时,最长的合唱队形
        //[][0] -> 此时为递增
        //[][1] -> 此时为递减
        int[][] dp = new int[n + 1][2];
        int max = 0;
        for(int i = 1;i <= n;i++) {
            Arrays.fill(dp[i], 1);
        }
        for(int i = 2;i <= n;i++) {
            //j代表i位置的上一个同学,查找能组成的最长序列
            for(int j = 1;j < i;j++) {
                if(arr[j] < arr[i]) {
                    //递增序列只能由递增序列得到
                    dp[i][0] = Math.max(dp[i][0], dp[j][0] + 1);
                }
                if(arr[j] > arr[i]) {
                    //递减序列可以由递减序列,或者递增序列得到
                    dp[i][1] = Math.max(dp[i][1], Math.max(dp[j][0] + 1,dp[j][1] + 1));
                }
            }
            max = Math.max(max, dp[i][0]);
            max = Math.max(max, dp[i][1]);
        }
        System.out.println(n - max);
    }
    // 蓝桥杯 蓝桥王国(⭐⭐⭐)
    public static int n;
    public static int m;
    public static long[] dis;
    public static boolean[] count;
    public static ArrayList<long[]>[] lists;
    public static long INF = 0x3f3f3f3f3f3f3f3fl;
    public static void main2(String[] args) throws IOException{
        n = in.nextInt();
        m = in.nextInt();
        dis = new long[n + 1];
        count = new boolean[n + 1];
        lists = new ArrayList[n + 1];
        for(int i = 0;i <= n;i++) {
            lists[i] = new ArrayList<>();
        }
        for(int i = 1;i <= m;i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            long c = in.nextLong();
            lists[a].add(new long[] {b,c});
        }
        dijkstra();
        for(int i = 1;i <= n;i++) {
            System.out.print((dis[i] == INF ? -1 : dis[i]) + " ");
        }
    }
    public static void dijkstra() {
        PriorityQueue<long[]> p = new PriorityQueue<long[]>(Comparator.comparing(k -> k[1]));
        Arrays.fill(dis, INF);
        dis[1] = 0;
        p.add(new long[] {1,0});
        while(!p.isEmpty()) {
            long[] t = p.poll();
            int index = (int)t[0];
            if(count[index]) continue;
            count[index] = true;
            for(long[] a:lists[index]) {
                int v = (int)a[0];
                long w = a[1];
                if(dis[v] > dis[index] + w) {
                    dis[v] = dis[index] + w;
                    p.add(new long[] {v,dis[v]});
                }
            }
        }
    }
}
class Read{
    StringTokenizer st = new StringTokenizer("");
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String next() throws IOException{
        while(!st.hasMoreTokens()){
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }
    int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
}